/**
 * LeetCode 121. 买卖股票的最佳时机
 */
public class Solution_121 {
    /**
     * 一次遍历
     * <p>
     * 时间复杂度：O(n)
     * <p>
     * 空间复杂度：O(1)
     */
    public int maxProfit(int[] prices) {
        if (prices.length < 2) {
            return 0;
        }
        // 初始化最大利润为0，历史最低价为第一天
        int maxProfit = 0, minPrice = prices[0];

        for (int i = 1; i < prices.length; i++) {
            // 更新历史最低价
            if (prices[i] < minPrice) {
                minPrice = prices[i];
            }
            // 更新最大利润
            if (prices[i] - minPrice > maxProfit) {
                maxProfit = prices[i] - minPrice;
            }
        }
        return maxProfit;
    }
}
